package xyf.p04.tree;

import commons.TreeNode;

import java.util.HashMap;

/**
 * ClassName: P0106_BuildTree
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:41 AM
 * Version: 1.0
 **/
public class P0106_BuildTree
{
    private HashMap<Integer, Integer> inMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder)
    {
        for (int i = 0; i < inorder.length; i++)
        {
            inMap.put(inorder[i], i);
        }

        return dfs(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode dfs(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight)
    {
        if (postLeft > postRight)
        {
            return null;
        }

        int rootVal = postorder[postRight];

        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inMap.get(rootVal);

        int leftLength = rootIndex - inLeft;

        root.left = dfs(inorder, postorder, inLeft, rootIndex - 1, postLeft, postLeft + leftLength - 1);

        root.right = dfs(inorder, postorder, rootIndex + 1, inRight, postLeft + leftLength, postRight - 1);

        return root;
    }
}